/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package boom;

/**
 *
 * @author kaaz
 */
public class Node implements Comparable<Node>{
    
    public Node left;
    public Node right;
    public Node parent;
    public int height; //childs
    public final Comparable value;
    
    Node(Comparable value){
        this.value = value;
    }
    
    public int getBalanceValue() {
        int leftChilds = (this.left != null) ? this.left.height : -1;
        int rightChilds = (this.right != null) ? this.right.height : -1;
        return leftChilds - rightChilds;
    }
    
    public int countLeftHeight(){
        if(this.left != null){
            return this.left.height;
        }
        return 0;
    }
    
    public int countRightHeight(){
        if(this.right != null){
            return this.right.height;
        }
        return 0;
    }
    
    public int getMaxHeight(){
        if(this.left != null && this.right != null){
            return Math.max(this.left.height, this.right.height);
        }
        else if(this.left != null && this.right ==null){
            return this.left.height;
        }
        else if(this.right != null && this.left == null){
            return this.right.height;
        }
        return 0;
    }
    
    public Node getLeft(){
        return this.left;
    }
    
    public void addHeightCount(){
        this.height++;
        if(this.getBalanceValue() >= -1 && this.getBalanceValue() <= 1){
            if(this.parent != null){
                this.parent.addHeightCount();
            }
        }
        else{
            this.rebalance();
        }
    }
        
    public void rebalance(){
        if(this.getBalanceValue() == -2){
            if(this.right.getBalanceValue() <= 0){
                this.rotateRightRight();
            } else {
                this.rotateRightLeft();
            }
        } else if(this.getBalanceValue() == 2){
            if(this.left.getBalanceValue() >= 0){
                this.rotateLeftLeft();
            } else {
                this.rotateLeftRight();
            }
        }
    }
    
    private void rotateRightRight() {
        System.out.println("Rebalance: Right-Right");
        Node Oself,Oright,Orightright,OParent;
        Oself = this;
        OParent = this.parent;
        
        Oright = this.right;
        Orightright = Oright.right;
        Oself.right = Oright.left;
        if(Oself.right != null){
            Oself.right.parent = Oself;
        }
        Oright.left = Oself;
        Oself.parent = Oright;
        
        if(OParent == null){
            Oright.parent = null;
        } else {
            if(OParent.right == Oself){
                OParent.right = Oright;
            } else{
                OParent.left = Oright;
            }
            Oright.parent = OParent;
        }
        this.recalculateHeight(Oself);
        if(Oright.parent != null) {
            this.recalculateHeight(Oright.parent);
        }
    }
    
    private void rotateRightLeft() {
        System.out.println("Rebalance: Right-Left");
        Node Oself,Oright,Orightleft,OParent;
        Oself = this;
        OParent = this.parent;
        
        Oright = Oself.right;
        Orightleft = Oright.left;
        Oright.left = Orightleft.right;
        if(Oright.left != null){
            Oright.left.parent = Oright;
        }
        Oself.right = Orightleft.left;
        if(Oself.right != null){
            Oself.right.parent = Oself;
        }
        Orightleft.right = Oright;
        Oright.parent = Orightleft;
        Orightleft.left = Oself;
        Oself.parent = Orightleft;
        if(OParent == null){
            Orightleft.parent = null;
        }
        else{
            if(OParent.right == Oself){
                OParent.right = Orightleft;
            }
            else{
                OParent.left = Orightleft;
            }
            Orightleft.parent = OParent;
        }
        this.recalculateHeight(Oself);
        this.recalculateHeight(Oright);
    }
    
    private void rotateLeftLeft() {
        System.out.println("Rebalance: Left-Left");
        Node Oself,OLeft,Oleftleft,Oparent;
        Oself = this;
        Oparent = this.parent;
        OLeft = Oself.left;
        Oleftleft = OLeft.left;
        Oself.left = OLeft.right;
        if(Oself.left != null){
            Oself.left.parent = Oself;
        }
        OLeft.right = Oself;
        Oself.parent = OLeft;
        if(Oparent == null){
            OLeft.parent = null;
        }
        else{
            if(Oparent.right == Oself){
                Oparent.right = OLeft;
            }
            else{
                Oparent.left = OLeft;
            }
            OLeft.parent = Oparent;
        }
        this.recalculateHeight(Oself);
        if(OLeft.parent != null){
            this.recalculateHeight(OLeft.parent);
        }
    }
    
    private void rotateLeftRight() {
        System.out.println("Rebalance: Left-Right");
        Node Oself,Oleft,Oleftright,Oparent;
        Oself = this;
        Oparent = this.parent;
        Oleft = Oself.left;
        Oleftright = Oleft.right;
        Oself.left = Oleftright.right;
        if(Oself.left instanceof Node){
            Oself.left.parent = Oself;
        }
	Oleft.right = Oleftright.left;
        if(Oleft.right instanceof Node){
            Oleft.right.parent = Oself;
        }
        Oleftright.left = Oleft;
        Oleft.parent = Oleftright;
        Oleftright.right = Oself;
        Oself.parent = Oleftright;
        if(Oparent == null){
            Oleftright.parent = null;
        }
        else{
            if(Oparent.right == Oself){
                Oparent.right = Oleftright;
            }
            else{
                Oparent.left = Oleftright;
            }
            Oleftright.parent = Oparent;
        }
        this.recalculateHeight(Oself);
        this.recalculateHeight(Oleft);
    }
    
    public boolean setLeft(Node n){
        if(this.left == null){
            n.parent = this;
            this.left = n;
            this.addHeightCount();
	    System.out.println("Adding '"+n.value+"' to '"+n.parent.value+"'.");
            return true;
        } else {
            return this.left.add(n);
        }
    }
    
    public boolean setRight(Node n){
        if(this.right == null){
            n.parent = this;
            this.addHeightCount();
            this.right = n;
	    System.out.println("Adding '"+n.value+"' to '"+n.parent.value+"'.");
            return true;
        } else{
            return this.right.add(n);
        }
    }
    
    public Node getRight(){
        return this.right;
    }
    
    public boolean add(Node n){
        if(this.compareTo(n) > 0) {
            return this.setLeft(n);
        } else if(this.compareTo(n) < 0) {
            return this.setRight(n);
        }
        return false;
    }
    
    public void recalculateHeight(Node n){
        int orgHeight = n.height;
        if(n.left != null || n.right != null){
            n.height = n.getMaxHeight() + 1;
        } else{
            n.height = 0;
        }
        if(n.parent != null && orgHeight != n.height){
            recalculateHeight(n.parent);
        }
    }
    
    @Override
    public int compareTo(Node o) {
        return this.value.compareTo(o.value);
    }
}
